package 算法基础模板.chapter_03;

import java.util.Arrays;

/**
 * @author Summerday
 */
public class TopSort {
    final int N = 100050;
    int[] h, e, ne;
    int idx = 0;
    int[] d;

    {
        h = new int[N];
        Arrays.fill(h, -1);
        e = new int[N];
        ne = new int[N];
        d = new int[N];
    }

    void add (int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
        d[b]++; // 计算入度
    }

    boolean topsort () {
        int[] q = new int[N];
        int hh = 0, tt = -1;
        // 初始化入队 入度为0 的点
        for (int i = 1; i <= N; i++) {
            if (d[i] == 0) q[++tt] = i;
        }
        // bfs
        while (hh <= tt) {
            int t = q[hh++];
            // 枚举t的所有出边  t-> j
            for (int i = h[t]; i != -1; i = ne[i]) {
                int j = e[i];
                // 删掉t-> j  d[j]--  如果为0, 出队
                if (--d[j] == 0) q[++tt] = j;
            }
        }
        return tt == N - 1; // 所有的点都出队了
    }
}
